package org.hhchat.leetcode.brainteaser;

import java.util.Arrays;

/**
 * Created this one by HMH on 2017/10/3.
 */
public class code292_easy {

    static class Solution {
        int dp[] = new int[10000];

        public boolean canWinNim(int n) {
            Arrays.fill(dp, -1);
            return helper(n, dp);
        }

        public boolean helper(int n, int dp[]) {
            if (dp[n] != -1) {
                return dp[n]==1;
            }
            if (n <= 3) {
                dp[n]=1;
                return true;
            }
            dp[n - 1] = helper(n - 1, dp) ? 1 : 0;
            dp[n - 2] = helper(n - 2, dp) ? 1 : 0;
            dp[n - 3] = helper(n - 3, dp) ? 1 : 0;

            return dp[n - 1] == 0 || dp[n - 2] == 0 || dp[n - 3] == 0;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.canWinNim(42));
    }

}
